package algorithm;

import java.util.Arrays;

public class T00034 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution().searchRange(new int[]{1,1,2}, 1)));
    }

    static class Solution {
        public int[] searchRange(int[] nums, int target) {
            return new int[] {leftBound(nums, target), rightBound(nums, target)};
        }

        public int leftBound(int[] nums, int target) {
            if (nums == null || nums.length == 0) {
                return -1;
            }
            int left = 0, right = nums.length - 1;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] > target) {
                    right = mid - 1;
                } else if (nums[mid] < target) {
                    left = mid + 1;
                } else if (nums[mid] == target) {
                    right = mid - 1;
                }
            }
            if (left >= nums.length || left < 0) {
                return -1;
            }
            return nums[left] == target ? left : -1;
        }

        public int rightBound(int[] nums, int target) {
            int left = 0, right = nums.length - 1;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] < target) {
                    left = mid + 1;
                } else if (nums[mid] > target) {
                    right = mid - 1;
                } else if (nums[mid] == target) {
                    left = mid + 1;
                }
            }
            if (right < 0 || right >= nums.length) {
                return -1;
            }
            return nums[right] == target ? right : -1;
        }
    }
}
